package com.heima.DP.bag01;

import java.util.Scanner;

/**
 * @Author: Ethan Yankang
 * @Program: 面试必会代码
 * @Date: 2024-09-04 16:51
 **/
/*
*题目描述 小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。
* 这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。
* 小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。
* 输入描述
* 第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。
* 第二行包含 M 个正整数，代表每种研究材料的所占空间。第三行包含 M 个正整数，代表每种研究材料的价值。
*
* 输出描述
* 输出一个整数，代表小明能够携带的研究材料的最大价值。
*
* 输入示例 6 1
2 2 3 1 5 2
2 3 1 5 4 3
*
* 输出示例 5
*
* 提示信息 小明能够携带 6 种研究材料，但是行李空间只有 1，而占用空间为 1 的研究材料价值为 5，所以最终答案输出 5。
*
* 数据范围：
1 <= N <= 5000
1 <= M <= 5000
研究材料占用空间和价值都小于等于 1000
*/

    /*
     * @description 首先明确这是典型的01背包问题，四大件，物品数量为M，物品重量为w[i],物品价值为v[i],背包最大容量为N
     * @params dp[i][j] 表示在编号为0-i的物品里面任意取放进容量为j的背包，(一个仅能取一次)，所能获得的最大价值dp为多少！！
     * @return
     */

public class bag01TwoAndOneParam {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        //int M = input.nextInt();
        int M=6;
        //int bagWeight = input.nextInt();
        int bagWeight=5;
        int[] weight=new int[M];
        int[] value=new int[M];

        //for (int i = 0; i < M; i++) {
        //    weight[i]=input.nextInt();
        //}
        //for (int i = 0; i < M; i++) {
        //     value[i]=input.nextInt();
        //}

        weight=new int[]{2,2,3,1,5,2};
        value= new int[]{2,3,1,5,4,3};
        System.out.println(solveTwoParam(M,bagWeight,weight,value));
        System.out.println(solveOneParam(M,bagWeight,weight,value));
    }

    /*
     * @description 牛逼，一维数组区区6行代码！就可以解决01dp
     * @params
     * @return
     */

    private static int solveOneParam(int m, int bagWeight, int[] weight, int[] value) {
        //dp[j]定义为容量为j的背包最多能装下的物品价值！！！！！！！！！！！！！！！！！！！！！！！

        int[] dp=new int[bagWeight+1];
        dp[0]=0;
        //遍历物品
        for (int i = 0; i < m; i++) {
            for (int j = bagWeight; j >=weight[i]; j--) {//注意一定要相等！！！
                dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]);
                 System.out.print("dp["+j+"]=" + dp[j]+"\t");
            }
            System.out.println();
        }
        return dp[bagWeight];
    }


    /*
     * @description 也挺牛的，二维数组，区区10行代码就可以解决01dp问题
     * @params
     * @return
     */

    private static int solveTwoParam(int m, int bagWeight, int[] weight,int[] value) {
        //dp[i][j]定义为从编号为0-i的物品里面选取出任意多个的物品(一次仅能取一个)，装进承重范围在为j的背包里面，背包所能获得的最大价值。！！！！！！！！！！！！
        //注意这里容量是bagWeight+1

        int[][] dp=new int[m][bagWeight+1];

        //初始化dp[i][j]背包
        for (int j = weight[0]; j <= bagWeight; j++) {//注意一定要相等鸭！！
            dp[0][j]=value[0];
        }

        //先遍历物品
        for (int i = 1; i < m; i++) {
            //再遍历目前的背包承重量(注意这里一定要相等)
            for (int j = 1; j <=bagWeight; j++) {
                //放和不放的两种选择(为什么不放？因为放不下呀！).那为什么放了后，还要在两者之间选择？
                // 因为放进去了，你的总价值也不一定比之前没放的大！所以要取最大值！

                //放进
                if (j>=weight[i])
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
                //没放
                //如果装不下这个物品,那么就继承dp[i - 1][j]的值
                else
                    dp[i][j]=dp[i-1][j];
                System.out.print("dp["+i+"]["+j+"]=" + dp[i][j]+"\t");
            }
            System.out.println();
        }
        return dp[m-1][bagWeight];
    }


}
